package alo.p6;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//二叉树的遍历
public class Ergodic {

    //递归前序遍历DLR
    void preOrder(BinaryTreeNode root){
        if (root!=null){
            System.out.println(root.getData());
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }

    //非递归前序遍历
    void preOrderNonRecursive(BinaryTreeNode root){
        if (root==null) return;
        //使用栈结构，对结点进行保存
        Stack<BinaryTreeNode> stack=new Stack();

        while (true){
            //栈不为空，进行压栈操作
            while (root!=null){
                System.out.println(root.getData());
                stack.push(root);
                root=root.getLeft();
            }
            //如果栈为空，结束循环
            if (stack.isEmpty()) break;
            //在栈不为空的前提下，将root设为当前节点的右兄弟
            root=stack.pop();
            root=root.getRight();
        }
        return;
    }

    //递归中序遍历LDR
    void inOrder(BinaryTreeNode root){
        if (root!=null){
            preOrder(root.getLeft());
            System.out.println(root.getData());
            preOrder(root.getRight());
        }
    }

    //非递归中序遍历
    void inOrderNonRecursive(BinaryTreeNode root){
        if (root==null) return;
        Stack<BinaryTreeNode> stack=new Stack();
        while (true){
            while (root!=null){
                stack.push(root);
                root=root.getLeft();
            }
            if (stack.isEmpty()) break;
            root=stack.pop();
            System.out.println(root.getData());
            root=root.getRight();
        }
        return;
    }

    //递归后序遍历LRD
    void postOrder(BinaryTreeNode root){
        if (root!=null){
            preOrder(root.getLeft());
            preOrder(root.getRight());
            System.out.println(root.getData());
        }
    }

    //非递归后序遍历
    //后序遍历与前中遍历不类似，每个结点需要访问两次，只有第二次才进行getData
    void postOrderNonRecursive(BinaryTreeNode root){
        //使用一个栈
        Stack<BinaryTreeNode> stack=new Stack();
        while (true) {
            //不为空，一直向左深入
            if (root != null) {
                stack.push(root);
                root = root.getLeft();
            } else {
                if (stack.isEmpty()) {
                    System.out.println("Stack is Empty");
                } else if (stack.peek().getRight() == null) {
                    root = stack.pop();
                    System.out.println(root.getData());
                    //当出栈时，判断该元素是否是栈顶元素的右孩子，如是，则代表已完成左右孩子的遍历
                    if (root == stack.peek().getRight()) {
                        System.out.println(stack.peek().getData());
                        stack.pop();
                    }
                }
                if (!stack.isEmpty()) {
                    root = stack.peek().getRight();
                } else root = null;
            }
        }
    }
    //利用两个栈实现后序遍历
    void postOrderNonRecursive2(BinaryTreeNode root){
        if (root!=null){
            Stack<BinaryTreeNode> stack1=new Stack<>();
            Stack<BinaryTreeNode> stack2=new Stack<>();
            stack1.push(root);
            while (!stack1.isEmpty()){
                root=stack1.pop();
                stack2.push(root);
                if (root.getLeft()!=null){
                    stack1.push(root.getLeft());
                }
                if (root.getRight()!=null){
                    stack1.push(root.getRight());
                }
            }
            while (stack1.isEmpty()){
                System.out.println(stack2.pop().getData());
            }
        }
    }

    void postOrderNonRecursive3(BinaryTreeNode root){
        if(root!=null){
            Stack<BinaryTreeNode> stack=new Stack<>();
            stack.push(root);
            BinaryTreeNode temp;
            while (!stack.isEmpty()){
                temp=stack.peek();
                //root不是temp的孩子，且temp的左孩子的不为空，则将temp的左孩子压栈
                if (temp.getLeft()!=null&&root!=temp.getLeft()&&root!=temp.getRight()){
                    stack.push(temp.getLeft());
                }
                //root不是temp的右孩子，且temp的右孩子的不为空，则将temp的右孩子压栈
                else if (temp.getRight()!=null&&root!=temp.getRight()){
                    stack.push(temp.getRight());
                }
                //1、temp的左右孩子为空，即代表temp的左右结点都访问过了
                //2、root为temp右孩子，即代表temp的左右结点都访问过了
                else {
                    System.out.println(stack.pop());
                    root=temp;
                }
            }
        }
    }

    //层续遍历
    public void levelOrder(BinaryTreeNode root){
        BinaryTreeNode temp;
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        if (root==null) return;
        queue.offer(root);
        while (!queue.isEmpty()){
            temp=queue.poll();
            System.out.println(temp.getData());
            if (temp.getLeft()!=null) queue.offer(temp.getLeft());
            if (temp.getRight()!=null) queue.offer(temp.getRight());
        }
    }
}
